// 括号字符串的有效性和最长有效长度

#include <iostream>
#include <string>
#include <stack>
#include <vector>

using namespace std;

class Solution {
public:

    // 括号字符串的有效性
    bool solution1(const string& str) {
        if (str.size() < 2) { return false; }
        stack<char> flag;
        // 统计左右括号的数量
        int leftCount = 0;
        int rightCount = 0;
        for (auto c : str) {
            if (c == '(') {
                leftCount++;
            } else if (c == ')'){
                rightCount++;
            } else {
                return false;
            }
            // 任意时刻 右括号多于左括号就直接返回
            if (rightCount > leftCount) { return false; }
        }

        return true;
    }

    int solution2(const string& str) {
        // 利用dp数组 记录以str[i]为结尾的最长有效字串
        vector<int> dp (str.size(), 0);
        int res = 0;
        int pre = 0;
        for (int i = 1; i < str.size(); i++) {
            if (str[i] == ')') {
                pre = i - dp[i - 1] - 1;
                if (pre >= 0 && str[pre] == '(') {
                    dp[i] = dp[i - 1] + 2 + (pre > 0 ? dp[pre - 1] : 0);
                }
                res = max(res, dp[i]);
            } 
        }
        return res;
    }
};


int main() {
    string testStr1 = "()()";
    string testStr2 = ")()()";
    Solution solu;
    cout << solu.solution1(testStr1) << " " << solu.solution1(testStr2) << endl;

    cout << solu.solution2(testStr1) << " " << solu.solution2(testStr2) << endl;

    return 0;
}